package aufgabe1;

import java.awt.Color;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Benny
 * 
 */
public class RedBlackTree_own<T> {
	private Node<T> root = null;
	private final Node<T> externalNode = new Node<T>();
	private final int MAX_CHILDREN = 2;

	private int maxPathLength;
	private TreeForm _tf;

	public RedBlackTree_own() {
		root = new Node<T>(externalNode);

	}

	/**
	 * Fuegt den Wert in den Baum ein
	 * 
	 * @param key
	 *            Wert der eingefuegt werden soll
	 * @param comp
	 *            Comperator zum vergleichen der Werte
	 */
	public void insert(T key, Comparator<T> comp) {
		if (root.key == null) {
			root.key = key;
			return;
		}
		Node<T> z = new Node<T>(key);

		Node<T> y = externalNode;
		Node<T> x = root;
		while (x != externalNode) {
			y = x;
			if (comp.compare(z.key, x.key) < 0) {
				x = x.left;
			} else {
				x = x.right;
			}
		}
		z.parent = y;
		if (y == externalNode) {
			root = z;
		} else if (comp.compare(z.key, y.key) < 0) {
			y.left = z;
		} else {
			y.right = z;
		}
		z.left = externalNode;
		z.right = externalNode;
		z.color = Color.RED;
		insertFixUp(z);
	}

	/**
	 * Stellt die Rot-Schwarz-Eigenschaften wieder her
	 * 
	 * @param z
	 *            Knoten der eingefügt wird
	 */
	private void insertFixUp(Node<T> z) {
		Node<T> y = null;
		while (z.parent.color == Color.RED) {
			if (z.parent == z.parent.parent.left) {
				y = z.parent.parent.right;
				// erster Fall
				if (y.color == Color.RED) {
					z.parent.color = Color.BLACK;
					y.color = Color.BLACK;
					z.parent.parent.color = Color.RED;
					z = z.parent.parent;
				} else {
					if (z == z.parent.right) {
						// 2ther Fall
						z = z.parent;
						rotateLeft(z);
					} else {
						// 3ther Fall
						z.parent.color = Color.BLACK;
						z.parent.parent.color = Color.RED;
						rotateRight(z.parent.parent);
					}

				}
			} else {
				y = z.parent.parent.left;
				// erster Fall
				if (y.color == Color.RED) {
					z.parent.color = Color.BLACK;
					y.color = Color.BLACK;
					z.parent.parent.color = Color.RED;
					z = z.parent.parent;
				} else {
					if (z == z.parent.left) {
						// zweiter Fall
						z = z.parent;
						rotateRight(z);
					} else {
						// 3ther Fall
						z.parent.color = Color.BLACK;
						z.parent.parent.color = Color.RED;
						rotateLeft(z.parent.parent);
					}
				}
			}
		}
		root.color = Color.BLACK;
	}

	/**
	 * * Voraussetzung x.right != externalNode *
	 * 
	 * @param x
	 *            Knoten um den nach links rotiert wird
	 */
	
	private void rotateLeft(Node<T> x) {
		Node<T> y = x.right;
		x.right = y.left;
		y.left.parent = x;
		y.parent = x.parent;
		if (x.parent == externalNode) {
			root = y;
		} else {
			if (x == x.parent.left) {
				x.parent.left = y;
			} else {
				x.parent.right = y;
			}
		}
		y.left = x;
		x.parent = y;
	}

	/**
	 * Noch testen Voraussetzung x.left != externalNode
	 * 
	 * @param x
	 *            Knoten um den nach recht rotiert wird
	 */

	private void rotateRight(Node<T> x) {
		Node<T> y = x.left; // bestimme y
		x.left = y.right; // mache y´s linker Teilbaum zu x´s rechtem
		y.right.parent = x;
		y.parent = x.parent;
		if (x.parent == externalNode) {
			root = y;
		} else {
			if (x == x.parent.left) {
				x.parent.left = y;
			} else {
				x.parent.right = y;
			}
		}
		y.right = x;
		x.parent = y;
	}

	/**
	 * a recursive method for calculating the maximum path length
	 */

	private void getMaxPathLength(Node<T> n, int depth) {

		if (n.left != externalNode) {

			getMaxPathLength(n.left, depth + 1);
		}
		if (depth > maxPathLength) {
			maxPathLength = depth;
		}

		if (n.right != externalNode) {

			getMaxPathLength(n.right, depth + 1);
		}
		if (depth > maxPathLength) {
			maxPathLength = depth;
		}
	}

	public int getDepth() {
		getMaxPathLength(root, 0);
		return maxPathLength;
	}

	public Node<T> getRoot() {
		return this.root;
	}

	public void showTreeGraphic(String title) {
		_tf = new TreeForm(root, title);
	}

	public class Node<T> {
		private Node<T> parent, left, right = null;

		private Color color = Color.BLACK;
		private T key = null;

		/**
		 * Spzieller Knoten statt Null
		 */
		private Node<T> externalNode;

		private Node() {
			this.parent = this.externalNode;
			this.left = this.externalNode;
			this.right = this.externalNode;
		}

		private Node(T key) {
			this();
			this.key = key;
		}

		private Node(T key, Node<T> parent) {
			this(key);
			this.parent = parent;
		}

		/**
		 * Returns true if node is a leaf
		 * 
		 * @return
		 */
		public boolean isLeaf() {

			if (getLeft() == externalNode && getRight() == externalNode) {
				return true;

			} else
				return false;
		}

		public int maxChildrens() {
			return MAX_CHILDREN;
		}

		public Node<T> getChild(int i) {
			if (i == 0) {
				return getLeft();
			} else
				return getRight();
		}

		private Node(Node<T> external) {
			this.externalNode = external;
			this.parent = this.externalNode;
			this.left = this.externalNode;
			this.right = this.externalNode;
		}

		public Node<T> getNode() {
			return this;
		}

		public Node<T> getParent() {
			return parent;
		}

		public void setParent(Node<T> parent) {
			this.parent = parent;
		}

		public Node<T> getLeft() {
			return left;
		}

		public void setLeft(Node<T> left) {
			this.left = left;
		}

		public Node<T> getRight() {
			return right;
		}

		public void setRight(Node<T> right) {
			this.right = right;
		}

		public Color getNodeColor() {
			return color;
		}

		public void setNodeColor(Color nodeColor) {
			this.color = nodeColor;
		}

		public T getKey() {
			return key;
		}

		public void setKey(T key) {
			this.key = key;
		}

		@Override
		public String toString() {
			return "Node [color=" + color + ", key=" + key + "]";
		}
	}
}